package com.murphy.algorithm.likou;


import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 二叉树按层输出
 * @author dongsufeng
 * @version 4.0
 * @date 2023/2/24 11:46
 */
public class TreeLevelPrint {

    public List<List<Integer>> print(TreeNode root){
        List<List<Integer>> lists = new ArrayList<>();

        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int count = 0;
        int size = deque.size();
        List<Integer> levelList = new ArrayList<>();
        while (!deque.isEmpty()){
            TreeNode curr = deque.pop();
            levelList.add(curr.val);
            count++;

            if (curr.l!=null){
                deque.offer(curr.l);
            }
            if (curr.r!=null){
                deque.offer(curr.r);
            }
            if (count==size){
                lists.add(levelList);
                levelList = new ArrayList<>();
                count = 0;size=deque.size();
            }
        }
        return lists;
    }

    public List<List<Integer>> print1(TreeNode root){
        List<List<Integer>> lists = new ArrayList<>();

        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);

        while (!deque.isEmpty()){
            List<Integer> levelList = new ArrayList<>();
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = deque.poll();
                levelList.add(curr.val);
                if (curr.l!=null){
                    deque.offer(curr.l);
                }
                if (curr.r!=null){
                    deque.offer(curr.r);
                }
            }
            lists.add(levelList);
        }
        return lists;
    }

    public static class TreeNode {
        private int val;
        private TreeNode l;
        private TreeNode r;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(5);
        TreeNode treeNode3 = new TreeNode(3);
        treeNode.l = treeNode3;
        TreeNode treeNode2 = new TreeNode(2);
        treeNode.l.l = treeNode2;
        TreeNode treeNode4 = new TreeNode(4);
        treeNode.l.r = treeNode4;

        TreeNode treeNode7 = new TreeNode(7);
        treeNode.r = treeNode7;
        TreeNode treeNode6 = new TreeNode(6);
        treeNode.r.l = treeNode6;
        TreeNode treeNode8 = new TreeNode(8);
        treeNode.r.r = treeNode8;

        TreeLevelPrint treeLevelPrint = new TreeLevelPrint();
        List<List<Integer>> list = treeLevelPrint.print(treeNode);
        System.out.println(JSON.toJSON(list));

        List<List<Integer>> list1 = treeLevelPrint.print1(treeNode);
        System.out.println(JSON.toJSON(list1));
    }
}
